//直接插入排序

// 分组，有序序列和无序序列

#include <iostream>

using namespace std;

//数组插入 0-3  012
int insertPart(int arr[],int i_begin,int i_end)
{
    //把end插入到begin-end-1中
    if(arr==NULL)
    {
        return 0;
    }
    if(arr[i_end]>=arr[i_end-1])
    {
        return 1;
    }
    //找到要插入的位置
    int index = 0;
    for(int i =0;i<i_end;i++)
    {
        if(arr[i]>arr[i_end])
        {
            index = i;
            break;
        }
    }
    int tmp = arr[i_end];
    //整体向后移
    for(int i = i_end-1;i>=index;i--)
    {
        arr[i+1] = arr[i];
    }
    arr[index]=tmp;
    return 1;
}

int insertSort(int arr[],int n)
{
    for(int i = 1;i<n;i++)
    {
        insertPart(arr,0,i);
    }
    return 1;
}
int main()
{
    int arr[] = {5,6,3,9,2,7,1};
    insertSort(arr,7);

    for(int i = 0;i<7;i++)
    {
        cout<<arr[i]<<",";
    }

    system("pause");
    return 0;
}
